/**
 * @author Sebastian
 * @version 2.0
 * @date 2024/7/2 20:59
 */
// 二叉树中的最大路径和
    // https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/
public class Solution124 {
    /**
     对于任意一个节点, 如果最大和路径包含该节点, 那么只可能是两种情况:
     1. 其左右子树中所构成的和路径值较大的那个加上该节点的值后向父节点回溯构成最大路径
     2. 左右子树都在最大路径中, 加上该节点的值构成了最终的最大路径
     **/
    private int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        res = getmax(root);
        return res;
    }

    // 每遍历到一个节点，我们都要求出包含该节点在内的此时的最大路径，并且在之后的遍历中更新这个最大值
    private int getmax(TreeNode root) {
        if (root == null) return 0;
        int left = Math.max(0, getmax(root.left));
        int right = Math.max(0, getmax(root.right));
        res = Math.max(res, left + right + root.val);
        // 但是还存在一个问题，那就是left和right具体应该怎么求，也就是left和right的递归形式
        // 我们要明确left和right的基本含义，它们表示的是最大贡献，那么一个节点的最大贡献就等于node.val+max(left,right)
        return Math.max(left, right) + root.val;
    }
}
